package edu.cityu.cs.hk.datastructures;
import java.util.Iterator;

//begin#fragment DFS
/** Generic depth first search traversal of a graph using the template method 
  * pattern. A subclass should override various methods to add functionality. */
public abstract class DFS {
  protected Graph G;                 // The graph being traversed
  protected Object visitResult;      // The result of the traversal
  protected static Object STATUS = new Object();    // The status attribute
  protected static Object VISITED = new Object();   // Visited value
  protected static Object UNVISITED = new Object(); // Unvisited value
  /** Execute a depth first search traversal on graph g, starting
    * from a vertex v, optionally passing in an information object (info) 
//end#fragment DFS
    * @param g Input graph.
    * @param start Start vertex of the traversal.
    * @param info Auxiliary information (to be used by subclasses). 
//begin#fragment DFS
    */
  public abstract Object execute(Graph g, Vertex start, Object info);
  /** Initialize the graph g for a traversal. */
  protected void init(Graph g) {
    G = g;
    for(Iterator vertices = g.vertices(); vertices.hasNext(); )
      unVisit((DecorablePosition)vertices.next());
    for(Iterator edges = g.edges(); edges.hasNext(); )
      unVisit((DecorablePosition)edges.next());    
  }
//end#fragment DFS

//begin#fragment DFS2
  /** Recursive template method for a generic DFS traversal.
    * @param v Start vertex of the traversal
    * @return result of the traversal
    */
  protected Object dfsTraversal(Vertex v) {
    initResult();
    if (!isDone())
      startVisit(v);
    if (!isDone()) {
      visit(v);
      for (Iterator inEdges = G.incidentEdges(v); inEdges.hasNext(); ) {
	Edge nextEdge = (Edge) inEdges.next();
	if (!isVisited(nextEdge)) {
	  // found an unexplored edge, explore it
	  visit(nextEdge);
	  Vertex w = G.opposite(v, nextEdge);
	  if (!isVisited(w)) { 
	    // w is unexplored, this is a discovery edge
	    traverseDiscovery(nextEdge, v);
	    if (isDone())
	      break;
	    visitResult = dfsTraversal(w);
	    if (isDone())
	      break;
	  }
	  else { 
	    // w is explored, this is a back edge
	    traverseBack(nextEdge, v);
	    if (isDone())
	      break;
	  }
	}
      }
    }
    if(!isDone())
      finishVisit(v);
    return result();
  }
  //end#fragment DFS2
  
  //begin#fragment decorations
  /** Mark a position as visited.	*/
  protected void visit(DecorablePosition p) { p.put(STATUS, VISITED); }
  /** Mark a position as unvisited.	*/
  protected void unVisit(DecorablePosition p) { p.put(STATUS, UNVISITED); }
  /** Test if a position has been visited. */
  protected boolean isVisited(DecorablePosition p) { 
    return (p.get(STATUS) == VISITED); 
  }
//end#fragment decorations

//begin#fragment auxiliary
  // Auxiliary methods (all initially null) for specializing a generic DFS 
  /** Initializes result (called first, once per vertex visited). */
  protected void initResult() {}          
  /** Called when we encounter a vertex (v). */
  protected void startVisit(Vertex v) {}  
  /** Called after we finish the visit for a vertex (v). */
  protected void finishVisit(Vertex v) {} 
  /** Called when we traverse a discovery edge (e) from a vertex (from). */
  protected void traverseDiscovery(Edge e, Vertex from) {} 
  /** Called when we traverse a back edge (e) from a vertex (from). */
  protected void traverseBack(Edge e, Vertex from) {}
  /** Determines whether the traversal is done early. */
  protected boolean isDone() { return false; /* default value */ } 
  /** Returns a result of a visit (if needed). */
  protected Object result() { return null; /* default value */ }
//end#fragment auxiliary
//begin#fragment Tail
}  // end of DFS abstract class
//end#fragment Tail

